package _76

import (
	. "GoLeetcode/common"
	"math"
	"sort"
)

/*
时间复杂度：O(N)
空间复杂度：O(1)

https://leetcode-cn.com/problems/maximum-running-time-of-n-computers/

解决m个电池给n台电脑供电，能让n台电脑同时运行的最长时间
*/

func maxRunTime(n int, batteries []int) int64 {
	sort.Slice(batteries, func(i, j int) bool {
		return batteries[i] > batteries[j]
	})
	var sum int64
	for _, v := range batteries {
		sum += int64(v)
	}
	for _, v := range batteries {
		if int64(v) > sum/int64(n) {
			sum -= int64(v)
			n--
		} else {
			return sum / int64(n)
		}
	}
	return -1
}

/*
时间复杂度：O(NlogN)
空间复杂度：O(1)

*/

func maxRunTime1(n int, batteries []int) int64 {
	l, r := 1, int(math.Pow(10, 16))
	for l < r {
		mid := (l + r) / 2
		if check(batteries, mid, n) {
			l = mid + 1
		} else {
			r = mid
		}
	}
	// 最后l==r, 而r的位置可能是不满足条件的，所以是l-1
	return int64(l - 1)
}

func check(arr []int, k, n int) bool {
	var sum int64
	for _, v := range arr {
		sum += int64(Min(v, k))
	}
	return sum/int64(k) >= int64(n)
}
